package closed_islands

var dirs = [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

func closedIsland(grid [][]int) (res int) {
	m, n := len(grid), len(grid[0])
	for i := 0; i < n; i++ {
		dfs(grid, 0, i)
		dfs(grid, m-1, i)
	}
	for i := 0; i < m; i++ {
		dfs(grid, i, 0)
		dfs(grid, i, n-1)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if 0 == grid[i][j] {
				res++
				dfs(grid, i, j)
			}
		}
	}
	return
}

func dfs(grid [][]int, i, j int) {
	m, n := len(grid), len(grid[0])
	if i < 0 || i >= m || j < 0 || j >= n {
		return
	}
	if grid[i][j] == 1 {
		return
	}
	grid[i][j] = 1
	for index := 0; index < len(dirs); index++ {
		next_i := i + dirs[index][0]
		next_j := j + dirs[index][1]
		dfs(grid, next_i, next_j)
	}
}
